#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

struct node {
	int w, v;
	node(int wi, int vi) {
		w = wi;
		v = vi;
	}
};

struct point {
	int w, id;
	point(int wi, int i) {
		w = wi;
		id = i;
	}
	bool operator < (const point x)const {
		return x.w < this->w;
	}
};

int n;
vector<node> G[1005];
priority_queue<point> h;
bool S[1005];

int main() {
	int m;
	scanf("%d", &m);
	for (int iux = 1; iux <= m; ++iux) {
		scanf("%d", &n);
		int wi;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				scanf("%d", &wi);
				if (i == j) continue;
				G[i].push_back(node(wi, j));
			}
		}
		
		int ans = 0;
		int index = 1;
		h.push(point(0, 1));
		while (index <= n) {
			int x = h.top().id, d = h.top().w;
			h.pop();
			if (S[x]) continue;
			S[x] = 1;
			++index;
			ans = max(ans, d);
			for (int i = 0; i < G[x].size(); ++i) {
				int y = G[x][i].v, z = G[x][i].w;
				if (!S[y]) {
					h.push(point(z, y));
				}
			}
		}
		printf("%d\n", ans);
		for (int i = 0; i <= n + 1; ++i) {
			G[i].clear();
		}
		while (h.size()) {
			h.pop();
		}
		for (int i = 0; i <= n; ++i) {
			S[i] = 0;
		}
	}
	return 0;
}
